package pprg.mergesort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MergeSort {

	private static int threshold;
	private static List<Thread> threads = Collections.synchronizedList(new ArrayList<Thread>());

	
	public static void sequentialMergeSort(int[] a) {
		
		if (a.length >= 2) {
			int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
			int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
			sequentialMergeSort(left);
			sequentialMergeSort(right);
			merge(left, right, a);
		}
	}

	public static void parallelMergeSort(int[] a, int threshold) {
		setThreshold(threshold);
		threads = new ArrayList<Thread>();
		if (a.length > threshold)
			parallelMergeSort(a, true);
		else
			parallelMergeSort(a, false);
	}

	public static void parallelMergeSort(int[] a, boolean parallel) {
		if (!parallel) {
			sequentialMergeSort(a);
		} else {
			int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
			int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);

			Thread lThread, rThread;
			if (left.length > threshold) {
				lThread = new Thread(new MergeSortWorker(left, true));
			} else {
				lThread = new Thread(new MergeSortWorker(left, false));
			}
			if (right.length > threshold) {
				rThread = new Thread(new MergeSortWorker(right, true));
			} else {
				rThread = new Thread(new MergeSortWorker(right, false));
			}

			threads.add(lThread);
			threads.add(rThread);
			lThread.start();
			rThread.start();

			try {
				lThread.join();
				rThread.join();
			} catch (InterruptedException ie) {
			}

			merge(left, right, a);
		}
	}

	public static void merge(int[] left, int[] right, int[] a) {
		int i1 = 0;
		int i2 = 0;
		for (int i = 0; i < a.length; i++) {
			if (i2 >= right.length
					|| (i1 < left.length && left[i1] < right[i2])) {
				a[i] = left[i1];
				i1++;
			} else {
				a[i] = right[i2];
				i2++;
			}
		}
	}

	public static int getThreshold() {
		return threshold;
	}

	public static void setThreshold(int threshold) {
		MergeSort.threshold = threshold;
	}

	public static int getNumberOfThreads() {
		if (threads != null) {
			return threads.size();
		} else {
			return 0;
		}
	}
}
